package com.practice.binarysearch;

public class UnboundedSearch {
	public boolean find(UnboundedArray<Integer> a, int target) {
		int upper = 1;
		while (a.get(upper)!=null && target>a.get(upper)) {
			upper = upper * 2;
		}
		return find(a, target, upper/2, upper);
	}
	
	private boolean find(UnboundedArray<Integer> a, int target, int lower, int upper) {
		if (upper < lower) return false;
		int i = (lower + upper) / 2;
		if (a.get(i)==null || a.get(i)>target) {
			return find(a, target, lower, i-1);
		}
		else if (a.get(i) == target) {
			return true;
		}
		else {
			return find(a, target, i+1, upper);
		}
	}
}
